//package work;
//
//import java.util.*;
//
//class Graph {
//    public HashMap<Integer, Node> nodes;
//    public HashSet<Edge> edges;
//
//    public Graph(){
//        nodes = new HashMap<>();
//        edges = new HashSet<>();
//    }
//
//    //广度优先遍历d
//    public void bfs(Node node){
//        if(node==null){
//            return;
//        }
//        Queue<Node> queue = new LinkedList<>();//bfs，队列储存了遍历顺序
//        HashSet<Node> hashSet = new HashSet<>();//防止重复遍历
//        hashSet.add(node);
//        queue.offer(node);
//        while (!queue.isEmpty()) {
//            Node n = queue.poll();
//            System.out.println(n.value);
//            ArrayList<Node> nexts = n.nexts;
//            for (Node next : nexts) {
//                if (!hashSet.contains(next)) {
//                    queue.offer(next);
//                    hashSet.add(next);
//                }
//            }
//        }
//    }
//
//    public void dfs(Node node){
//        if(node==null){
//            return;
//        }
//        Stack<Node> stack = new Stack<>();
//        stack.push(node);
//        HashSet<Node> hashSet = new HashSet<>();
//        hashSet.add(node);
//        System.out.println(node.value);
//        while(!stack.isEmpty()){
//            Node cur = stack.pop();
//            ArrayList<Node> nexts = cur.nexts;
//            for (Node next : nexts) {
//                if(!hashSet.contains(next)){
//                    hashSet.add(cur);
//                    hashSet.add(next);
//                    System.out.println(next.value);
//                }
//            }
//        }
//
//    }
//
//    public List<Node> sortedTopology(Graph graph) {
//        if (graph == null) {
//            return null;
//        }
//
//        HashMap<Node, Integer> hashMap = new HashMap<>();
//        Queue<Node> queue = new LinkedList<>();
//
//        List<Node> result = new ArrayList<>();
//        for (Node node : graph.nodes.values()) {
//            hashMap.put(node, node.in);
//            if (node.in == 0) {
//                queue.offer(node);
//            }
//        }
//
//        while (!queue.isEmpty()) {
//            Node cur = queue.poll();
//            result.add(cur);
//            for (Node next : cur.nexts) {
//                hashMap.put(next, hashMap.get(next) - 1);
//                if (hashMap.get(next) == 0) {
//                    queue.offer(next);
//                }
//            }
//        }
//        return result;
//    }
//
//    public Graph createGraph(char[][] grid){
//        Graph graph = new Graph();
//        HashMap<Integer, Node> nodes = graph.nodes;
//        //遍历
//        for (int i = 0; i < grid.length; i++) {
//            for (int j = 0; j < grid[0].length; j++) {
//                if(grid[i][j]=='1'){//找到节点
//                    int weight = i*grid.length+j;
//                    //判断节点是否存在图内，
//                    if(!nodes.containsKey(weight)){
//                        nodes.put(weight,new Node(weight));
//                    }
//                    Node node = nodes.get(weight);
//                    //判断上下左右，四个方向有没有节点
//                    if(i>0&&grid[i-1][j]=='1'){
//                        int underWeight = (i-1)*grid.length+j;
//                        if(!nodes.containsKey(weight)){
//                            nodes.put(underWeight,new Node(underWeight));
//                        }
//                        Node underNode = nodes.get(underWeight);
//                        //在node节点next列表添加节点
//                        node.nexts.add(underNode);
//                        //创造Edge边与添加边
//                        Edge underEdge = new Edge(weight,node,underNode);
//                        node.edges.add(underEdge);
//                        graph.edges.add(underEdge);
//                        //入度出度
//                        node.out++;
//                        underNode.in--;
//                    }
//
//                    if(i<grid.length-1&&grid[i+1][j]=='1'){
//                        int onWeight = (i+1)*grid.length+j;
//                        if(!nodes.containsKey(weight)){
//                            nodes.put(onWeight,new Node(onWeight));
//                        }
//                        Node onNode = nodes.get(onWeight);
//                        //在node节点next列表添加节点
//                        node.nexts.add(onNode);
//                        //创造Edge边与添加边
//                        Edge onEdge = new Edge(weight,node,onNode);
//                        node.edges.add(onEdge);
//                        graph.edges.add(onEdge);
//                        //入度出度
//                        node.out++;
//                        onNode.in--;
//                    }
//                    if(j>0&&grid[i][j-1]=='1'){
//                        int leftWeight = i*grid.length+j-1;
//                        if(!nodes.containsKey(weight)){
//                            nodes.put(leftWeight,new Node(leftWeight));
//                        }
//                        Node leftNode = nodes.get(leftWeight);
//                        //在node节点next列表添加节点
//                        node.nexts.add(leftNode);
//                        //创造Edge边与添加边
//                        Edge leftEdge = new Edge(weight,node,leftNode);
//                        node.edges.add(leftEdge);
//                        graph.edges.add(leftEdge);
//                        //入度出度
//                        node.out++;
//                        leftNode.in--;
//                    }
//                    if(i>0&&grid[i-1][j]=='1'){
//                        int rightWeight = i*grid.length+j+1;
//                        if(!nodes.containsKey(weight)){
//                            nodes.put(rightWeight,new Node(rightWeight));
//                        }
//                        Node rightNode = nodes.get(rightWeight);
//                        //在node节点next列表添加节点
//                        node.nexts.add(rightNode);
//                        //创造Edge边与添加边
//                        Edge rightEdge = new Edge(weight,node,rightNode);
//                        node.edges.add(rightEdge);
//                        graph.edges.add(rightEdge);
//                        //入度出度
//                        node.out++;
//                        rightNode.in--;
//                    }
//
//                }
//            }
//        }
//        return graph;
//    }
//
////    public int numIslands(char[][] grid) {
////        Graph graph = createGraph(grid);
////        UnionFindSet unionFindSet = new UnionFindSet((List<Integer>) graph.nodes.keySet());
////        HashSet<Node> result = new HashSet<>();
////        for (Edge edge : graph.edges) {
////            int from = edge.from.value;
////            int to = edge.to.value;
////            unionFindSet.union(from,to);
////        }
////
////        for (Node value : unionFindSet.fatherMap.values()) {
////            result.add(value);
////        }
////
////        return result.size();
////    }
//}
